#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <sys/time.h>

#define MAX_N 100000
#define ALGORITHMS_NUM 5

typedef struct UnionFind* UF;

struct UnionFind{
    int* id;
    int* sz;    // 仅用于加权算法
    int N;
    int setNum;
    int edges;
    int rootP;
    int rootQ;
};

// 时间获取函数（毫秒精度）
long get_time_ms() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec * 1000 + tv.tv_usec / 1000;
}

//quick-find find
int qf_find(UF uf, int p, int q) {
    return uf->id[p] == uf->id[q];
}

//quick-find union
void qf_union(UF uf, int p, int q) {
    int t = uf->id[p];
    for (int i = 0; i < uf->N; i++) {
        if (t == uf->id[i]) {
            uf->id[i] = uf->id[q];
        }
    }
    uf->setNum--;
    uf->edges++;

}

// 快速合并（Quick-Union）
int qu_find(UF uf, int p, int q) {
    int i, j;
    for (i = uf->id[p]; i != uf->id[i]; i = uf->id[i]) {
        ;
    }
    for (j = uf->id[q]; j != uf->id[j]; j = uf->id[j]) {
        ;
    }
    uf->rootP = i;
    uf->rootQ = j;
    return i == j;
}

void qu_union(UF uf, int p, int q) {
    int rootP = uf->rootP;
    int rootQ = uf->rootQ;
    uf->id[rootP] = rootQ;
    uf->setNum--;
    uf->edges++;
}

// 加权快速合并（Weighted QU）
int wqu_find(UF uf, int p, int q) {
    int i, j;
    for (i = uf->id[p]; i != uf->id[i]; i = uf->id[i]) {
        ;
    }
    for (j = uf->id[q]; j != uf->id[j]; j = uf->id[j]) {
        ;
    }
    uf->rootP = i;
    uf->rootQ = j;
    return i == j;
}

void wqu_union(UF uf, int p, int q) {
    int rootP = uf->rootP;
    int rootQ = uf->rootQ;
    
    if (uf->sz[rootP] < uf->sz[rootQ]) {
        uf->id[rootP] = rootQ;
        uf->sz[rootQ] += uf->sz[rootP];
    } else {
        uf->id[rootQ] = rootP;
        uf->sz[rootP] += uf->sz[rootQ];
    }
    uf->setNum--;
    uf->edges++;
}

// 带路径压缩的加权QU（Full Path Compression）
int pc_full_find(UF uf, int p, int q) {
    int i, j;
    for (i = uf->id[p]; i != uf->id[i]; i = uf->id[i]) {
        ;
    }
    int rootP = i;
    for (i = uf->id[p]; i != uf->id[i]; i = uf->id[i]) {
        uf->id[i] = rootP;
    }
    for (j = uf->id[q]; j != uf->id[j]; j = uf->id[j]) {
        ;
    }
    int rootQ = j;
    for (j = uf->id[q]; j != uf->id[j]; j = uf->id[j]) {
        uf->id[j] = rootQ;
    }

    uf->rootP = i;
    uf->rootQ = j;
    return i == j;
}

// 带路径压缩的加权QU（half Path Compression）
int pc_half_find(UF uf, int p, int q) {
    int i, j;
    for (i = uf->id[p]; i != uf->id[i]; i = uf->id[i]) {
        uf->id[i] = uf->id[uf->id[i]];
    }
    for (j = uf->id[q]; j != uf->id[j]; j = uf->id[j]) {
        uf->id[j] = uf->id[uf->id[j]];
    }

    uf->rootP = i;
    uf->rootQ = j;
    return i == j;
}

void pc_union(UF uf, int p, int q) {
    wqu_union(uf, p, q);  // 复用加权合并逻辑
}

UF initUF(int N, int alg){
    UF uf = malloc(sizeof(struct UnionFind));
    uf->N = N;
    uf->setNum = N;
    uf->edges = 0;
    uf->id = malloc(N * sizeof(int));
    if (alg >= 2){
        uf->sz = malloc(N * sizeof(int));
    }
    // 初始化
    for (int i = 0; i < N; i++) {
        uf->id[i] = i;
        if (alg >= 2){
            uf->sz[i] = 1;
        }
    }
    return uf;

}

long test_algorithm(UF uf, int N, int alg) {
    int (*find)(UF, int, int);
    void (*union_op)(UF, int, int);
    
    // 算法选择
    switch(alg) {
        case 0:  // Quick-Find
            find = qf_find;
            union_op = qf_union;
            break;
        case 1:  // Quick-Union
            find = qu_find;
            union_op = qu_union;
            break;
        case 2:  // Weighted QU
            find = wqu_find;
            union_op = wqu_union;
            break;
        case 3:  // Path Compression By Full
            union_op = pc_union;
            find = pc_full_find;
            break;
        case 4:  // Path Compression By Half
            union_op = pc_union;
            find = pc_half_find;
            break;
    }
    // 执行测试
    long start = get_time_ms();
    
    while (uf->setNum > 1) {
        int p = rand() % N;
        int q = rand() % N;
        if (!find(uf, p, q)) {
            union_op(uf, p, q);
        }
    }

    long elapsed = get_time_ms() - start;
    return elapsed;
}

void destroyUF(UF uf, int alg){
    free(uf->id);
    if (alg >= 2) {
        free(uf->sz);
    }
}

int main() {
    srand(time(NULL));
    
    int test_cases[] = {1000, 2500, 5000, 10000, 25000, 50000, 100000};
    int case_len = sizeof(test_cases)/sizeof(int);
    const char* algorithms[] = {"F", "U", "W", "P", "H"};
    
    printf("| %-7s | %-7s | %-4s | %-4s | %-4s | %-4s |%-4s |\n", 
           "N", "M", "F", "U", "W", "P", "H");
    printf("|---------|---------|------|------|------|------|------|\n");

    for (int i = 0; i < case_len; i++) {
        int N = test_cases[i];
        
        long times[ALGORITHMS_NUM] = {0};
        int M = 0;
        int mArray[ALGORITHMS_NUM] = {0};
        for (int alg = 0; alg < ALGORITHMS_NUM; alg++) {
            UF uf = initUF(N, alg);
            times[alg] += test_algorithm(uf, N,alg);
            mArray[alg]+= uf->edges;
            destroyUF(uf, alg);
        }
        int sumM = 0;
        for (int t = 0; t < ALGORITHMS_NUM; t++) {
            sumM += mArray[t];
        }
        M = sumM / ALGORITHMS_NUM;

        // 输出结果
        printf("| %-7d | %-7d | %-4ld | %-4ld | %-4ld | %-4ld | %-4ld |\n",
               N, M, 
               times[0], 
               times[1],
               times[2],
               times[3],
               times[4])
               ;
    }
    
    return 0;
}